Largest Sub-array Sum
Problem: To find the maximum sum of a contiguous sub-array within the given array. The sub-array should be contiguous.
Input: Given a one-dimensional array A of size n, where A contains n elements. The elements can have either positive or negative values.
Output: The maximum sum of a contiguous sub-array.
Video Lecture
Largest Sub-array Sum – Example
Algorithm
LargestSubArraySum(A[0]..A[n-1])
Input: Array A containing n elements.
Output: Largest sum of contiguous sub-array.
Step 1: Start.
Step 2: Input array A.
Step 3: Initialize current_max and max_sofar with A[0].
Step 4: For i = 1 to n-1, do the following:
Step 5: If A[i] > current_max + A[i], then set current_max = A[i];
else set current_max = current_max + A[i].
Step 6: If current_max > max_sofar, then set max_sofar = current_max.
Step 7: Repeat Step 4.
Step 8: Return max_sofar, then Stop.
Algorithm Analysis:
Time Complexity T(n) = O(n).
Largest Sub-array
#include <stdio.h>
int MaxMin(int A[], int n, int i,int max, int min) {
while ( i<= n) {
if (A[i]<min)
min=A[i];
if (A[i]>min)
max=A[i];
i++;
}
printf(" Maximum Value is = %d", max);
printf(" Minimum Value is = %d", min);
}
void InputArray(int A[], int n)
{
int i;
printf("Enter the %d Elements\n",n);
for (i = 0; i < n; i++)
{
printf("i =%d \t", i);
scanf("%d",&A[i]);
}
}
// Driver Code
int main(void) {
int A[100],n,min, max;
printf("Enter the size of the array \n");
scanf("%d",&n);
InputArray(A,n);
MaxMin(A,n-1,1,A[0],A[0]);
return 0;
}
#include <iostream>
#include <vector>
#include <climits>
int maxSubArraySum(const std::vector<int>& nums) {
int maxSum = INT_MIN;
int currentSum = 0;
for (int num : nums) {
currentSum += num;
if (maxSum < currentSum)
maxSum = currentSum;
if (currentSum < 0)
currentSum = 0;
}
return maxSum;
}
int main() {
std::vector<int> nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
std::cout << "Maximum Subarray Sum is " << maxSubArraySum(nums) << std::endl;
return 0;
}
public class LargestSumSubarray {
public static int maxSubArraySum(int[] nums) {
int maxSum = Integer.MIN_VALUE;
int currentSum = 0;
for (int num : nums) {
currentSum += num;
if (maxSum < currentSum)
maxSum = currentSum;
if (currentSum < 0)
currentSum = 0;
}
return maxSum;
}
public static void main(String[] args) {
int[] nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
System.out.println("Maximum Subarray Sum is " + maxSubArraySum(nums));
}
}
def max_subarray_sum(nums):
max_sum = float('-inf')
current_sum = 0
for num in nums:
current_sum += num
if max_sum < current_sum:
max_sum = current_sum
if current_sum < 0:
current_sum = 0
return max_sum
nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
print("Maximum Subarray Sum is", max_subarray_sum(nums))
Analysis of Largest Sub-array Sum
Time Complexity
The recursive algorithm is used to find T(n), where T(n) represents the time taken to find the largest sum of a sub-array. The recurrence relation for Merge Sort is:
T(n) = 2T(n/2)
T(n/2) = 2T(n/4), …
According to the Master Theorem:
T(n) = n.logn
T(n) = n.logn
T(n) = O(n.logn)
